package com.code.test.second.dp;

/**
 * https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0343.%E6%95%B4%E6%95%B0%E6%8B%86%E5%88%86.md
 * <p>
 * <p>
 * 343. 整数拆分
 * 力扣题目链接
 * <p>
 * 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
 * <p>
 * 示例 1:
 * <p>
 * 输入: 2
 * 输出: 1
 * 解释: 2 = 1 + 1, 1 × 1 = 1。
 * 示例 2:
 * <p>
 * 输入: 10
 * 输出: 36
 * 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
 * 说明: 你可以假设 n 不小于 2 且不大于 58。
 */
public class SCode342 {

    /**
     * 只有数值近似相等，相乘才可能最大
     *
     * @param args
     */
    public static void main(String[] args) {
        System.out.println(integerBreak(10));
    }

    /**
     * 1、dp[i] 对i进行拆分，得到的最大乘积dp[i]
     * 2、dp[i] = j*dp[i-j]
     * 3、初始化
     */

    public static int integerBreak(int n) {
        int[] dp = new int[n + 1];

        dp[2] = 1;//2-1=1*dp[1]=1*1

        /**
         * 基本思路是把dp[i]拆成 j*dp[i-j]
         * i=6,可拆成
         * 1*5 j*(i-j)  5还可以继续拆，也是 j*(i-j)，所以
         * 2*4
         * 3*3
         * 4*2
         *
         */
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j <= i - j; j++) {
                /**
                 * j*(i-j)是简单的把一个数拆成 j和 i-j
                 * 然后再跟 i-j拆了之后的进行对比，看看哪个大
                 * eg:
                 * 6 = 1*(6-1)=5
                 * 1*(5-1) = 4
                 * max(5,4)
                 */
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }


}
